Định lý Fermat khẳng định với mọi số nguyên tố p và mọi số a:

a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} .

Nếu p là số nguyên tố lẻ, từ đó có

a p − 1 2 ≡ ± 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}} .

Định nghĩa

Số tự nhiên lẻ n thoả mãn đồng dư thức tương tự với một a nào đó:

a n − 1 2 ≡ ± 1 ( mod n ) {\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}} .

được gọi là số nguyên tố xác suất Euler, nếu n là hợp số thì n dược gọi là số giả nguyên tố Euler.

Các kết quả

1. Mọi số giả nguyên tố Euler cơ sở a đều là số giả nguyên tố Fermat cơ sở a.